priority_queue K I
1. Definition
An instance Q of the parameterized data type is a
collection of items (type pq). Every item contains a key from type
K and an information from the linearly ordered type I. K is called the
key type of Q and I is called the information type of Q. The number of
items in Q is called the size of Q. If Q has size zero it is called the
empty priority queue. We use < k, i > to denote a pq
with key k and
information i.
2. Creation
a) Q
b)
<
K, I, prio
> Q;
creates an instance of type and initializes it with the
empty priority queue. Variant a) chooses the default data structure
(cf. 4.1.4), and variant b) chooses class
prio as the
implementation of the queue (cf. section 9 for a list of possible
implementation parameters).
3. Operations
& truecm & truecm & K key pq_item it returns the key of item it. it is an item in .
I inf pq_item it returns the information of item it. it is an item in . pq_item insert K k,I i adds a new item < k, i > to and returns it. pq_item find_min returns an item with minimal information (nil if is empty) void del_item pq_item it removes the item it from . it is an item in . K del_min removes the item it = .find_min() from and returns the key of it. is not empty. void decrease_inf pq_item it, I i makes i the new information of item it it is an item in and i is not larger then inf (it). void change_key pq_item it, K k makes k the new key of item it it is an item in . void clear makes the empty priority queue bool empty returns true, if is empty, false otherwise int size returns the size of .
4. Implementation
Priority queues are implemented by Fibonacci heaps ([FT84]. Operations insert, del_item, del_min take time O(log n), find_min, decrease_inf, key, inf, empty take time O(1) and clear takes time O(n), where n is the size of . The space requirement is O(n).
5. Example
Dijkstra's Algorithm (cf. section 8.1)